package lab2;

import java.util.AbstractSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * реализация структуры TreeSet
 */
public class MyTreeSet extends AbstractSet<Integer> {

	/**
	 * корень дерева
	 */
	private Node root = null;
	private int size = 0;

	public MyTreeSet() {
		this.root = null;
	}

	private class Node {
		public Integer value;
		public Node parent;
		public Node left;
		public Node right;

		public Node(Node parent, Integer i) {
			this.value = i;
			this.parent = parent;
			this.left = null;
			this.right = null;
		}
	}

	/**
	 * нахождение минимального узла в поддереве с вершиной curNode
	 * @param curNode
	 * @return самый нижний левый лист в поддереве - то есть лист с минимальным значением в поддереве или null, если curNode==null
	 */
	private Node findMin(Node curNode) { 	

		if (curNode == null) {
			return null;
		}
		if (curNode.left == null) {
			return curNode;
		}
		Node MinNode = curNode.left;
		return findMin(MinNode);
	}

	private class MyIterator implements Iterator<Integer> {
		private Node nextNode = null;

		public MyIterator(Node nextNode) {
			this.nextNode = nextNode;
		}

		/**
		 * проверка, есть ли следующий элемент в дереве
		 */
		public boolean hasNext() {
			return nextNode != null;
		}

		/**
		 * вершина, слева от которой все листы уже посещены
		 * @param myNode - лист, начиная с которого мы ищем 
		 * @return первый верхний лист, который по значению больше myNode или null, если myNode - корень дерева 
		 */
		private Node firstRightUp(Node myNode) {  
			if (myNode.parent == null) {
				return null;
			}
			if (myNode.parent.value < myNode.value) {
				return firstRightUp(myNode.parent);
			} else if (myNode.parent.value > myNode.value) {
				return myNode.parent;
			}
			return null;
		}

		/**
		 * поиск следующего по порядку возрастания значений узла в дереве
		 * @return значение следующего по порядку возрастания значений узла
		 * @throws NoSuchElementException если следующего элемента в дереве нет
		 */
		public Integer next() throws NoSuchElementException {
			if (nextNode == null) {
				throw new NoSuchElementException();
			}
			Integer i = nextNode.value;
			if (nextNode.right != null) {
				nextNode = findMin(nextNode.right);
			} else {
				nextNode = firstRightUp(nextNode);
			}
			return i;
		}

		@Override
		public void remove() {
			// TODO Auto-generated method stub
			throw new UnsupportedOperationException();
		}

	}
	
	/**
	 * первый лист: самый нижний левый
	 */
	public MyIterator iterator() {					  
		if (this.root == null) {
			return null;
		}
		Node myNode = findMin(this.root);
		MyIterator iter = new MyIterator(myNode);
		return iter;
	}
	
	/**
	 * вершина, слева от которой все листы уже посещены (функция для методов myTreeSet)
	 * @param myNode - лист, начиная с которого мы ищем 
	 * @return первый верхний лист, который по значению больше myNode или null, если myNode - корень дерева 
	 */
	private Node firstRightUpNode(Node myNode) {   
		if (myNode.parent == null) {
			return null;
		}
		if (myNode.parent.value < myNode.value) {
			return firstRightUpNode(myNode.parent);
		} else if (myNode.parent.value > myNode.value) {
			return myNode.parent;
		}
		return null;
	}

	/**
	 * поиск следующего по порядку возрастания значений узла в дереве
	 * @param nextNode - узел, относительно которого нужно найти следующий
	 * @return следующий по порядку возрастания значений узел или null, если на вход подан null
	 */
	private Node nextNode(Node nextNode) {
		if (nextNode == null) {
			return null;
		}
		if (nextNode.right != null) {
			nextNode = findMin(nextNode.right);
		} else {
			nextNode = this.firstRightUpNode(nextNode);
		}
		return nextNode;
	}

	/**
	 * Количество элементов в дереве
	 */
	@Override
	public int size() { 							 
		return this.size;
	}

	/**
	 * функция для метода add
	 * @param myNode - узел, к которому данный метод добавит ребенка
	 * @param i - значение, которое будет у узла, которого создаст данный метод
	 * @return true, если узел успешно создан или false, если не создан, так как узел с таким значением уже есть
	 */
	private boolean addToNode(Node myNode, Integer i) { 
		if (i > myNode.value) {
			if (myNode.right == null) {
				myNode.right = new Node(myNode, i);
				this.size++;
				return true;
			} else {
				return addToNode(myNode.right, i);
			}
		} else if (i < myNode.value) {
			if (myNode.left == null) {
				myNode.left = new Node(myNode, i);
				this.size++;
				return true;
			} else {
				return addToNode(myNode.left, i);
			}
		} else {
			return false;
		}
	}

	/**
	 * добавление узда со значением i
	 * @param i - значение узла, который нужно добавить в дерево
	 * @return true, если узел успешно создан или false, если не создан, так как узел с таким значением уже есть
	 * @throws NullPointerException если на вход подается null
	 */
	@Override
	public boolean add(Integer i) throws NullPointerException{
		if (i==null) {
			throw new NullPointerException();
		}
		if (this.root == null) {
			this.root = new Node(null, i);
			this.size++;
			return true;
		} else {
			return addToNode(this.root, i);
		}
	}

	/**
	 * функция для метода contains
	 * @param myNode - узел, со значением которого сравнивается значение искомого узла 
	 * @param i - значение искомого узла
	 * @return true, если узел найден или false, если узел не найден
	 */
	private boolean containsToNode(Node myNode, Integer i) { 
		if (i == myNode.value) {
			return true;
		} else if (i > myNode.value) {
			if (myNode.right == null) {
				return false;
			} else {
				return containsToNode(myNode.right, i);
			}
		} else {
			if (myNode.left == null) {
				return false;
			} else {
				return containsToNode(myNode.left, i);
			}
		} 
	}
	
	/**
	 * проверка, содержится ли в дереве узел с указанным значением
	 * @param num - значение искомого узла
	 * @return true, если узел найден или false, если узел не найден
	 * @throws NullPointerException если на вход подается null
	 */
	public boolean contains(Integer num) throws NullPointerException {
		if (num==null) {
			throw new NullPointerException();
		}
		if (this.root == null) {
			return false;
		} else {
			return containsToNode(this.root, num);
		}
	}

	/**
	 * функция для remove
	 * @param delNode - узел, который нужно удалить
	 * @return true, если узел успешно удален
	 */
	private boolean removeNode(Node delNode) { 				
		if ((delNode.left == null) && (delNode.right == null)) { // у узла нет детей
			if (delNode.parent == null) {
				this.root = null;
			} else {
				if (delNode.value < delNode.parent.value) {
					delNode.parent.left = null;
				} else {
					delNode.parent.right = null;
				}
			}
			this.size--;
			return true;
		}
		if (delNode.right == null) { 					//  у узла только левый ребенок
			delNode.left.parent = delNode.parent;
			if (delNode.parent==null) {
				this.root=delNode.left;
			} else if (delNode.value < delNode.parent.value) {
				delNode.parent.left = delNode.left;
			} else {
				delNode.parent.right = delNode.left;
			}
			this.size--;
			return true;
		}
		if (delNode.left == null) { 					// у узла только правый ребенок
			delNode.right.parent = delNode.parent;
			if (delNode.parent==null) {
				this.root=delNode.right;
			} else if (delNode.value < delNode.parent.value) {
				delNode.parent.left = delNode.right;
			} else {
				delNode.parent.right = delNode.right;
			}
			this.size--;
			return true;
		} else { // если у узла есть оба ребенка
			Node exchangeNode = findMin(delNode.right);
			delNode.value = exchangeNode.value;
			return removeNode(exchangeNode);
		}
	}

	/**
	 * удаление узла со значением num
	 * @param num - значение узла, который нужно удалить, если он существует
	 * @return true, если узел успешно удален или false, если такой узел не найден
	 * @throws NullPointerException если на вход подается null
	 */
	public boolean remove(Integer num) throws NullPointerException{
		
		if (num==null) {
			throw new NullPointerException();
		}
		if (this.root == null) {
			
			return false;
		}
		
		Node leftNode = this.findMin(this.root);
		if (leftNode.value == num) {
			return removeNode(leftNode);
		}
		
		while (this.nextNode(leftNode) != null) {
			if (this.nextNode(leftNode).value == num) {
				return removeNode(this.nextNode(leftNode));
			}
			leftNode = this.nextNode(leftNode);
		}
		return false;
	}

	/**
	 * проверка, пустое ли дерево
	 * @return true, если дерево пустое или false, если дерево не пустое
	 */
	public boolean isEmpty() {
		return this.root == null;
	}

	/**
	 * очистка дерева
	 */
	public void clear() {
		this.root = null;
	}

	/**
	 * представление дерева в виде строки
	 * @return строку со всеми узлами а порядке возрастания их значений
	 */
	public String toString() {
		StringBuilder TreeString = new StringBuilder("");
		if (this.root == null) {
			return TreeString.toString();
		}
		for (int i : this) {
			TreeString.append(i+" ");
		}
		return TreeString.toString();
	}
}
